1765. Three sequences

 

Three sequences of integers are given. Find the length of their longest common subsequence.

 

Input. Contains the description of three sequences. Each sequence in given with two lines. First line contains the length of the sequence n (1 ≤ n ≤ 100), and second line contains its elements (32 bits integers).

 

Output. Print the length of the longest common subsequence.

 

Sample input

Sample output

 
3
1 2 3
3
1 3 2
3
2 1 3

2

 

 

SOLUTION

dynamic programming – LCS

 

Algorithm analysis

Let a, b, c be three input sequences. Let f(i, j, k) be the length of LCS of sequences a[1..i], b[1..j] and c[1..k]. The value f(i, j, k) we shall keep in dp[i][j][k].

If a[i] = b[j] = c[k], then

f(i, j, k) = 1 + f(i – 1, j – 1, k – 1)

Otherwise

f(i, j, k) = max( f(i – 1, j, k), f(i, j – 1, k), f(i, j, k – 1) )

 

Algorithm realization

Store the input three sequences in arrays a, b, c. To compute their LCS, declare an array dp.

 

#define MAX 110

int a[MAX], b[MAX], c[MAX];

int dp[MAX][MAX][MAX];

 

Read three input sequences.

 

scanf("%d", &n);

for (i = 1; i <= n; i++) scanf("%d", &a[i]);

scanf("%d", &m);

for (i = 1; i <= m; i++) scanf("%d", &b[i]);

scanf("%d", &k);

for (i = 1; i <= k; i++) scanf("%d", &c[i]);

 

Compute LCS, fill the array dp.

 

for (u = 1; u <= n; u++)

for (v = 1; v <= m; v++)

for (w = 1; w <= k; w++)

{

  if ((a[u] == b[v]) && (a[u] == c[w]))

    dp[u][v][w] = dp[u - 1][v - 1][w - 1] + 1;

  else

   dp[u][v][w] = max(dp[u - 1][v][w], max(dp[u][v - 1][w], dp[u][v][w - 1]));

}

 

Print the answer.

 

printf("%d\n", dp[n][m][k]);